Blum–Shub–Smale Machine

In computation theory, the Blum–Shub–Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a Random Access Machine with registers that can store arbitrary real numbers and that can compute rational functions over reals in a single time step. It is often referred to as Real RAM model. BSS machines are more powerful than Turing machines, because the latter are by definition restricted to a finite alphabet. A Turing machine can be empowered to store arbitrary rational numbers in a single tape symbol by making that finite alphabet arbitrarily large (in terms of a physical machine using transistor-based memory, building its memory locations of enough transistors to store the desired number), but this does not extend to the uncountable real numbers (for example, no number of transistors can accurately represent Pi).

Definition

A BSS machine M is given by a list $I$of $N+1$ instructions (to be described below), indexed $0, 1, \dots, N$. A configuration of M is a tuple $(k,r,w,x)$, where ''k'' is the index of the instruction to be executed next, ''r'' and ''w'' are copy registers holding non-negative integers, and $x=(x_0,x_1,\ldots)$ is a list of real numbers, with all but finitely many being zero. The list $x$ is thought of as holding the contents of all registers of M. The computation begins with configuration $(0,0,0,x)$ and ends whenever $k=N$; the final content of ''x'' is said to be the output of the machine.

The instructions of M can be of the following types:
*Computation$(x_)$: a substitution $x_ := g_(x)$ is performed, where $g_$ is an arbitrary rational function (a quotient of two polynomial functions with arbitrary real coefficients); copy registers ''r'' and ''w'' may be changed, either by $r := 0$ or $r := r + 1$ and similarly for w. The next instruction is ''k''+1.
*Branch$(x_, l)$: if $x_ \geq 0$ then goto $l$; else goto ''k''+1.
*Copy($x_, x_$): the content of the "read" register $x_$ is copied into the "write" register $x_$; the next instruction is ''k''+1

See also

*Hypercomputation
*Real computer
*Real RAM

Further reading

*
*
*
*
{{DEFAULTSORT:Blum-Shub-Smale machine
Models of computation